package com.pogodin.wave;

import java.awt.Point;
import java.awt.Point;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Random;

public class Frog {
    
    private static int [][] arr;
    private static int n;
    private static int m;
    private static List<Point> mainList;


    public Frog() {
    }



    public int resolve(final List<Point> points, int currSumm){
        if(points.get(points.size() - 1).getX() == n - 1
                && points.get(points.size() - 1).getY() == m - 1){
           // System.out.println("finish" + currSumm);
            return currSumm;
        }        
        List<Point> ways = new ArrayList<Point>();
        int x = (int)points.get(points.size() - 1).getX();
        int y = (int)points.get(points.size() - 1).getY();
        if(x - 1 >= 0){
            ways.add(new Point(x - 1, y));
        }
        if(x + 1 < n){
            ways.add(new Point(x + 1, y));
        }
        if(y - 1 >= 0){
            ways.add(new Point(x, y - 1));
        }
        if(y + 1 < m){
            ways.add(new Point(x, y + 1));
        }
        int resultSumm = 0;
        for (Point way : ways) {
            //System.out.println("currentWay : " + way);
            if(!points.contains(way)){
               // System.out.println("way passes");
                List<Point> cloneList= new ArrayList<Point>(points);
                cloneList.add(way);
                int innerSumm = resolve(cloneList, currSumm + arr[(int)way.getX()][(int)way.getY()]);
                //System.out.println("inner sum for way :" + way + " sum " + innerSumm);
                if(innerSumm < resultSumm || resultSumm == 0){
                    resultSumm = innerSumm;
                    mainList = cloneList;
                }
            }
        }

        return resultSumm;
    }
    
    public static void main(String [] args){
        Random rand = new Random();
        arr = new int[rand.nextInt(10) + 1][rand.nextInt(10) + 1];
        Frog.n = arr.length;
        Frog.m = arr[0].length;

        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                arr[i][j] = rand.nextInt(10);
            }
        }

        Frog frog = new Frog();
        List<Point> inst = new ArrayList<Point>();
        inst.add(new Point(0,0));
        System.out.println(frog.resolve(inst, arr[0][0]));
        System.out.println(mainList);
        System.out.println(Arrays.deepToString(arr));
    }
}
